% 在读出data和求得精确查找结果的前提下
% 此程序用于离线建立索引和在线查找
clear;clc;
load('data.mat');
%%
% 设置需要在线查询的点数和查询的最近邻个数
onSearchPnum=1000;
% 找到最近的10个邻居索引，k=邻居数量
k = 10; 
% 离线建立索引
% 对每个点进行哈希映射到m个随机向量上
m=20;
w=0.05;
b=zeros(m,1);
as=zeros(m,32);
for i=1:m
    R=randn(1,32);as(i,:)=R;b(i)=w*rand;
end
hashTable=zeros(size(data,1),m);
for i=1:size(data,1)
    dot1=sum(as.*data(i,:),2);
    hashTable(i,:)=floor((dot1+b).'/w);
end

%%
% 在线查找
% 记录时间toc-tic=elapsedTime
countTime=0;
% 查询到的前onSearchPnum个点的k个最近邻
searchTop10=zeros(onSearchPnum,k);
for i=1:onSearchPnum
    indexSet=[];distances=[];
    selectedRows=[];sortedIndices=[];
    tic;
    % 获得近邻的候选index
    for j=1:m
        % 获取第i行第j列的值
        targetValue=hashTable(i,j);
        % 在第j列中查找与targetValue相同的值
        index=[];
        index=find(hashTable(:,j)==targetValue);
        % 将index添加到结果集合中,排除掉第i行
        indexSet=union(indexSet,index(index~=i));
    end
    % 精确查找前10个最近的点
    % 根据 indexSet 从 data 矩阵中取出对应的行
    selectedRows=data(indexSet, :);
    % 计算欧几里得距离，并找出最小的 k=10 个
    distances=sqrt(sum((selectedRows-data(i,:)).^2, 2));
    [minDistances,sortedIndices]=sort(distances);
    top10Indices=indexSet(sortedIndices(1:k)); 
    % 结束计时
    elapsedTime = toc;
    searchTop10(i,:)=top10Indices';
    countTime=countTime+elapsedTime;
end
% 输出平均时间
disp("在线查找所用的平均时间为：");
fprintf('%fs\n', countTime/1000);

%%
% 计算准确率，召回率=TP/(TP+FN),TP为同时在true（neares...）和search里面的，FN为不在search中在true（neares...）中的
acc=0;
recall=0;
for i=1:size(searchTop10,1)
    TP=sum(ismember(searchTop10(i,:),nearestNeighbors(i,:)));
    FN=k-TP;
    recall=recall+TP/(TP+FN);
    acc=acc+(size(data,1)-k-(k-TP)+TP)/size(data,1);
end
disp("准确率");
disp(acc/1000);
disp("召回率");
disp(recall/1000);

